package algorithm.binaryTree;

import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution2 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

//目标：给定二叉树的根节点 root ，返回所有左叶子之和。
class Solution404_2 {
    //方法：迭代法-用栈。只要把左叶子节点统计出来 - 这次用前序遍历吧-中左右
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;

        Stack<TreeNode> stack = new Stack<>();// 栈先进后出
        stack.push(root);//初始化
        int sum =0;
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left != null && node.left.left== null && node.left.right == null)
                sum += node.left.val;
            // 入栈顺序：右-左, 出栈进行处理的时候才先处理：左
            if(node.right != null)  stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        return sum;

    }
}

class Solution513 {
    public int findBottomLeftValue(TreeNode root) {
        //1：参数与返回值
        // 2终止条件：最底层、最左边
        // 3 单层处理 :是左叶子呀？





        return 0;

    }
}
//class Solution513_2 {
//    public int findBottomLeftValue(TreeNode root) {
//        //一层一层的遍历，，层次遍历用队列。
//        // 队列先进先出，可以按次序处理每一层。
//        // 使用 height 记录遍历到的节点的高度，curVal 记录高度在 curHeight 的最左节点的值。
//        //1,3；2,7，qu只要有高度就一直更新，所以取最新的那一个就行了。
//
//
//        Queue<TreeNode> queue = new LinkedList<>();
//        //初始。
//        queue.offer(root);
//        TreeNode node1 = null;
//        int flag = 0;//表示是底层，没有下一层了。
//        Map<Integer, Integer> map = new HashMap<>();
//
//        while (!queue.isEmpty()){
//            TreeNode node = queue.poll();
//            if (node.left != null) queue.offer(node.left);
//            if (node.right != null) queue.offer(node.right);
//            //处理： 找最底层
//            // 的左边的叶子节点
//            if(node.left == null && node.right == null) node1 = node;
//
//           if(queue.peek()== null)
//               //1、是最后一个，
//
//
//        }
//
//
//
//
//
//
//
//
//
//
//        return 0;
//
//    }
//}

class Solution404 {
    //方法：递归遍历
    public int sumOfLeftLeaves(TreeNode root) {
        //1：参数与返回值
        return sumLeft(root);
    }
    //求 所有左叶子之和,后序遍历（左右中）
    private int sumLeft(TreeNode root){
        // 2终止条件：左叶子空/叶子空
        // 3 单层处理 :是左叶子呀？
        if(root == null )
            return 0;
        int sum1= sumLeft(root.left);  // 左
        int sum2= sumLeft(root.right);  // 右
        // 中
        int sum =0;
        // 判断当前节点是不是左叶子是无法判断的，必须要通父节点来判断：
        //左叶子：如果【该节点的左节点】不为空，并且【该节点的左节点】的左节点为空 &&【该节点的左节点】的右节点为空
        if(root.left != null && root.left.left== null && root.left.right == null)
            sum += root.left.val;//该节点的左节点是左叶子

        return sum + sum1 +  sum2; //求所有的，子树上面的左叶子也加上。
    }
}


// 目标：二叉树的所有路径（从根节点到叶子节点）
// 方法2：广度优先-迭代法
class Solution257 {
    public List<String> binaryTreePaths(TreeNode root) {
        //一层一层的遍历，层次遍历用队列
        //如果到叶子节点，说明找到了一条完整路径
        //右子节点不为空就把右子节点和路径存放到队列中

        List<String> reslist = new ArrayList<>();
        if(root ==null) return reslist;
        Queue<Object> queue = new LinkedList<>();//为了同时存储节点和路径（密切的对应关系）
        //初始：节点和路径同时入对。
        // 节点和路径成对出现，路径就是从根节点到当前节点。
        queue.offer(root);
        queue.offer(root.val + "");

        while (!queue.isEmpty()){
            //同一层的是在不同的path上。
            TreeNode node = (TreeNode) queue.poll();
            String path = (String) queue.poll();
            if(node.left == null && node.right ==null){
                //到了叶子节点，路径就加入结果集。
                reslist.add(path);
                continue;
            }
            //没有到叶子节点。就对于此node, 继续遍历
            if(node.left != null) {
                queue.offer(node.left);
                //路径上要加上子节点了
                queue.offer(path +"->" + node.left.val );//在原路径上拼接上 ->  node.left.val
            }
            if(node.right != null) {
                queue.offer(node.right);
                queue.offer(path +"->" + node.right.val );
            }
        }
        return reslist;
    }
}


// 目标：二叉树的所有路径（从根节点到叶子节点）
// 方法1：深度优先搜索，递归法实现：
class Solution257_1 {
public List<String> binaryTreePaths(TreeNode root) {
    // 1 确定递归的参数与返回值：当前根节点，路径记录path，存放结果的集合。
    // 处理后，要继续遍历，不需要返回值
    List<String> resPath = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    findPath(root,sb, resPath); //初始化
    return resPath;
}
//递归法实现时
//只要当前节点非null，将当前节点加到路径path上，并且判断
// 如果当前节点是叶子节点，说明到终点了，目标路径就OK了，将当前路径加入到答案集合中。
//如果当前节点不是叶子节点，路径要继续拼接->，继续递归遍历左右分支。
// 递归法实现：1 确定递归的参数与返回值：当前要节点，路径记录path，存放结果的集合。
private void findPath(TreeNode root, StringBuilder path, List<String> res){
    //先遍历吧
    if(root == null) return;
    //root 不为null , 就加到路径上
    path.append(root.val);
    //是叶子节点？
    if(root.left == null && root.right == null){
       //如果当前节点是叶子节点，到终点了，目标路径就OK结束了，将当前路径加入到答案集合中。
        res.add(path.toString()); //直接就结束了，不用再往下遍历了。因为叶子就是路径的终点了，这条路径不会再多什么了。
        //是递归的终止条件
    }else {
        //不是叶子节点，path就继续拼接-> （  "1-> 2 ->"）,并且继续遍历
        path.append("->");
       //递归的单层处理逻辑：：遍历  递归遍历该节点的每一个child节点。
        // StringBuilder是可变的，参数不能传入path，否则传入path后回溯的path就被改变了。
        //任意一方左/右分支为 null 的话就没有必要继续往下遍历了。
        if(root.left != null)    findPath(root.left, new StringBuilder(path), res);
        if(root.right != null )  findPath(root.right, new StringBuilder(path), res);
    }
}

}



















}
